#pragma once
#include<vector>
#include<assert.h>

//最大堆
class Heap {
public:
	bool isEmpty() {
		return last == 0;
	}

	void push(int val) {
		if (data.size() <= last)
			data.push_back(val);
		else
			data[last] = val;
		int cur = last++;
		while ((cur - 1) / 2 >= 0  && data[(cur - 1) / 2] < data[cur]) {
			std::swap(data[(cur - 1) / 2], data[cur]);
			cur = (cur - 1) / 2;
		}
	}

	void pop() {
		assert(!isEmpty());
		std::swap(data[0], data[--last]);
		int cur = 0;
		while ((2 * cur + 1) < last) {
			int left = 2 * cur + 1;
			int right = 2 * cur + 2;
			int larger = left;
			if (right < last && (data[left] < data[right]))
				larger = right;
			if (data[larger] <= data[cur])
				break;
			std::swap(data[larger], data[cur]);
			cur = larger;
		}
	}

	const int& top() {
		assert(!isEmpty());
		return data[0];
	}

private:
	std::vector<int>data;
	int last = { 0 };
};
